package cn.com.leetcode.greedy;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 机器人在一个无限大小的网格上行走，从点 (0, 0) 处开始出发，面向北方。该机器人可以接收以下三种类型的命令：
 * <p>
 * -2：向左转 90 度
 * -1：向右转 90 度
 * 1 <= x <= 9：向前移动 x 个单位长度
 * 在网格上有一些格子被视为障碍物。
 * <p>
 * 第 i 个障碍物位于网格点  (obstacles[i][0], obstacles[i][1])
 * <p>
 * 机器人无法走到障碍物上，它将会停留在障碍物的前一个网格方块上，但仍然可以继续该路线的其余部分。
 * <p>
 * 返回从原点到机器人所有经过的路径点（坐标为整数）的最大欧式距离的平方。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/walking-robot-simulation
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Demo874 {
    public static void main(String[] args) {
        int[] commands = {1, 2, -2, 5, -1, -2, -1, 8, 3, -1, 9, 4, -2, 3, 2, 4, 3, 9, 2, -1, -1, -2, 1, 3, -2, 4, 1, 4, -1, 1, 9, -1, -2, 5, -1, 5, 5, -2, 6, 6, 7, 7, 2, 8, 9, -1, 7, 4, 6, 9, 9, 9, -1, 5, 1, 3, 3, -1, 5, 9, 7, 4, 8, -1, -2, 1, 3, 2, 9, 3, -1, -2, 8, 8, 7, 5, -2, 6, 8, 4, 6, 2, 7, 2, -1, 7, -2, 3, 3, 2, -2, 6, 9, 8, 1, -2, -1, 1, 4, 7};
        int[][] obstacles = {{-57, -58}, {-72, 91}, {-55, 35}, {-20, 29}, {51, 70}, {-61, 88}, {-62, 99}, {52, 17}, {-75, -32}, {91, -22}, {54, 33}, {-45, -59}, {47, -48}, {53, -98}, {-91, 83}, {81, 12}, {-34, -90}, {-79, -82}, {-15, -86}, {-24, 66}, {-35, 35}, {3, 31}, {87, 93}, {2, -19}, {87, -93}, {24, -10}, {84, -53}, {86, 87}, {-88, -18}, {-51, 89}, {96, 66}, {-77, -94}, {-39, -1}, {89, 51}, {-23, -72}, {27, 24}, {53, -80}, {52, -33}, {32, 4}, {78, -55}, {-25, 18}, {-23, 47}, {79, -5}, {-23, -22}, {14, -25}, {-11, 69}, {63, 36}, {35, -99}, {-24, 82}, {-29, -98}, {-50, -70}, {72, 95}, {80, 80}, {-68, -40}, {65, 70}, {-92, 78}, {-45, -63}, {1, 34}, {81, 50}, {14, 91}, {-77, -54}, {13, -88}, {24, 37}, {-12, 59}, {-48, -62}, {57, -22}, {-8, 85}, {48, 71}, {12, 1}, {-20, 36}, {-32, -14}, {39, 46}, {-41, 75}, {13, -23}, {98, 10}, {-88, 64}, {50, 37}, {-95, -32}, {46, -91}, {10, 79}, {-11, 43}, {-94, 98}, {79, 42}, {51, 71}, {4, -30}, {2, 74}, {4, 10}, {61, 98}, {57, 98}, {46, 43}, {-16, 72}, {53, -69}, {54, -96}, {22, 0}, {-7, 92}, {-69, 80}, {68, -73}, {-24, -92}, {-21, 82}, {32, -1}, {-6, 16}, {15, -29}, {70, -66}, {-85, 80}, {50, -3}, {6, 13}, {-30, -98}, {-30, 59}, {-67, 40}, {17, 72}, {79, 82}, {89, -100}, {2, 79}, {-95, -46}, {17, 68}, {-46, 81}, {-5, -57}, {7, 58}, {-42, 68}, {19, -95}, {-17, -76}, {81, -86}, {79, 78}, {-82, -67}, {6, 0}, {35, -16}, {98, 83}, {-81, 100}, {-11, 46}, {-21, -38}, {-30, -41}, {86, 18}, {-68, 6}, {80, 75}, {-96, -44}, {-19, 66}, {21, 84}, {-56, -64}, {39, -15}, {0, 45}, {-81, -54}, {-66, -93}, {-4, 2}, {-42, -67}, {-15, -33}, {1, -32}, {-74, -24}, {7, 18}, {-62, 84}, {19, 61}, {39, 79}, {60, -98}, {-76, 45}, {58, -98}, {33, 26}, {-74, -95}, {22, 30}, {-68, -62}, {-59, 4}, {-62, 35}, {-78, 80}, {-82, 54}, {-42, 81}, {56, -15}, {32, -19}, {34, 93}, {57, -100}, {-1, -87}, {68, -26}, {18, 86}, {-55, -19}, {-68, -99}, {-9, 47}, {24, 94}, {92, 97}, {5, 67}, {97, -71}, {63, -57}, {-52, -14}, {-86, -78}, {-17, 92}, {-61, -83}, {-84, -10}, {20, 13}, {-68, -47}, {7, 28}, {66, 89}, {-41, -17}, {-14, -46}, {-72, -91}, {4, 52}, {-17, -59}, {-85, -46}, {-94, -23}, {-48, -3}, {-64, -37}, {2, 26}, {76, 88}, {-8, -46}, {-19, -68}};
        Demo874 demo874 = new Demo874();
        int maxLen = demo874.robotSim(commands, obstacles);
        System.out.println(maxLen);
    }

    /**
     * 获取最小欧氏距离的平方
     *
     * @param commands
     * @param obstacles
     * @return
     */
    public int robotSim(int[] commands, int[][] obstacles) {
        int length = commands.length;
        int index[] = {0, 0}; //使用一维数组表示机器人的坐标
        int direction = 0; //使用书子表示方向，其中 0 表示北（上），1 表示东（右） 2 表示南（下） 3 表示东（坐）
        int maxLen = Integer.MIN_VALUE;
        Map<Integer, List<Integer>> obstacleMap = new HashMap<>();

        for (int[] obstacle : obstacles) {
            List<Integer> obstacleYList = obstacleMap.get(obstacle[0]);
            if (obstacleYList == null) {
                obstacleYList = new ArrayList<>();
            }
            obstacleYList.add(obstacle[1]);
            obstacleMap.put(obstacle[0], obstacleYList);
        }

        for (int i = 0; i < length; i++) {
            int command = commands[i];
            if (command < 0) {
                direction = getDirection(direction, commands[i]);
            } else {
                robotGo(index, direction, commands[i], obstacleMap);
                int euclideanMetric = (int) Math.pow(index[0], 2) + (int) Math.pow(index[1], 2);
                if (euclideanMetric > maxLen) {
                    maxLen = euclideanMetric;
                }
            }
        }

        return maxLen;
    }

    /**
     * 根据命令获取机器人的前进方向
     *
     * @param direction
     * @param turnTo
     * @return
     */
    private int getDirection(int direction, int turnTo) {

        if (turnTo == -1) {
            direction += 1;
        } else {
            direction -= 1;
        }
        return (direction + 4) % 4;
    }

    private void robotGo(int index[], int direction, int advanceDistance, Map<Integer, List<Integer>> obstacleMap) {
        int x = index[0];
        int y = index[1];
        if (direction == 0) {
            int i = 0;
            for (; i < advanceDistance; i++) {
                if (!isAgreeGo(x, y + i + 1, obstacleMap)) {
                    break;
                }
            }
            y = y + i;
        } else if (direction == 1) {
            int i = 0;
            for (; i < advanceDistance; i++) {
                if (!isAgreeGo(x + i + 1, y, obstacleMap)) {
                    break;
                }
            }
            x = x + i;
        } else if (direction == 2) {
            int i = 0;
            for (; i < advanceDistance; i++) {
                if (!isAgreeGo(x, y - i - 1, obstacleMap)) {
                    break;
                }
            }
            y = y - i;
        } else if (direction == 3) {
            int i = 0;
            for (; i < advanceDistance; i++) {
                if (!isAgreeGo(x - i - 1, y, obstacleMap)) {
                    break;
                }
            }
            x = x - i;
        }
        index[0] = x;
        index[1] = y;
    }

    /**
     * 是否同意向前前进一步的距离
     *
     * @param x
     * @param y
     * @param obstacleMap
     * @return
     */
    private boolean isAgreeGo(int x, int y, Map<Integer, List<Integer>> obstacleMap) {
        List<Integer> obstacleYList = obstacleMap.get(x);

        if (obstacleYList == null || obstacleYList.isEmpty()) {
            return true;
        }

        for (Integer obstacleY : obstacleYList) {
            if (obstacleY == y) {
                return false;
            }
        }

        return true;
    }


}
